package algorithm;



import util.GsonUtil;

/**
 * 快排
 * @Author Antony
 * @Since 2018/5/6 21:53
 */
public class QuickSort {

    public void test(){
        int[] arr = {10,4,67,9,33,5,12,7,10,17,2,67};
        quickSort(arr);
        System.out.println(GsonUtil.toJson(arr));
    }

    public static void quickSort(int[] arr){
        quickSort(arr, 0, arr.length-1);
    }


    public static void quickSort(int[] arr, int left, int right){
        if(left >= right){
            return;
        }

        int temp = arr[left];
        int i = left;
        int j = right;
        int t;

        while (i != j){
            //由于是以左为基准，所以先从右边查找。
            while (arr[j] >= temp && i<j){
                j--;
            }
            while (arr[i] <= temp && i<j){
                i++;
            }
            //都找到以后，交换两个Index中元素的位置
            if(i<j) {
                t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
            }
        }

        //基准数和ij相遇的数互换，也就是基准数归位
        arr[left] = arr[i];
        arr[i] = temp;

        //处理左边
        quickSort(arr,left, i-1);
        //处理右边
        quickSort(arr, i+1, right);
        return;
    }
}
